//
// Created by lwj12 on 24-8-22.
//

#ifndef PRIORITY_QUEUE_PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_PRIORITY_QUEUE_H
#include <ostream>
#include <vector>
using namespace std;

namespace lwj
{
    template<class T>
    struct less
    {
        bool operator()(const T& t1, const T& t2) const
        {
            return t1 < t2;
        }
    };

    template<class T>
    struct greater
    {
        bool operator()(const T& t1, const T& t2) const
        {
            return t1 > t2;
        }
    };

    template<class T, class Compare = less<T>, class Container = vector<T>>
    class PriorityQueue
    {
    public:
        void AdjustDown(size_t father)
        {
            size_t child = 2 * father + 1;
            while(child < size())
            {
                if(child + 1 < size() && _com(_con[child], _con[child + 1])) child++;
                if(_com(_con[father], _con[child]))
                {
                    swap(_con[father], _con[child]);
                    father = child;
                    child = 2 * father + 1;
                }
                else break;
            }
        }

        void AdjustUp(size_t child)
        {
            int father = (child - 1) / 2;
            while (father >= 0)
            {
                if(_com(_con[father], _con[child]))
                {
                    swap(_con[father], _con[child]);
                    child = father;
                    father = (child - 1) / 2;
                }
                else break;
            }
        }

        PriorityQueue() = default;
        template<class InputIterator>
        PriorityQueue(InputIterator first, InputIterator last)
            : _con(first, last)
        {
            //_con.assign(first, last);
            for(int i = ( _con.size() - 2) / 2; i >= 0; i--)
            {
                AdjustDown(i);
            }
        }

        PriorityQueue(initializer_list<T> il)
                :_con(il)
        {
            for(int i = ( _con.size() - 2) / 2; i >= 0; i--)
            {
                AdjustDown(i);
            }
        }

        const T& top() const {return _con.front();}
        size_t size() const {return _con.size();}

        void push(const T& val)
        {
            _con.push_back(val);
            AdjustUp(_con.size() - 1);
        }

        void pop()
        {
             _con[0] = _con[_con.size() - 1];
             _con.pop_back();
             AdjustDown(0);
        }

        bool empty() {return _con.empty();}
    private:
        Container _con;
        Compare _com;
    };
}

#endif//PRIORITY_QUEUE_PRIORITY_QUEUE_H
